package sort

func QuickSort(arr []int) {
	quick(0, uint(len(arr))-1, arr)
}

func quick(l, r uint, arr []int) {

	if l < r {
		i, j := l, r
		x := arr[l]
		for i < j {
			for i < j && arr[j] >= x {
				j--
			}
			if i < j {
				arr[i] = arr[j]
				i++
			}
			for i < j && arr[i] < x {
				i++
			}
			if i < j {
				arr[j] = arr[i]
				j--
			}
		}
		arr[i] = x
		quick(l, i-1, arr)
		quick(i+1, r, arr)

	}
}
